package com.zdp.leetcodeMiddle;

/*
* 题目描述：
* 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 跳跃游戏_55 {
    public static void main(String[] args) {
        跳跃游戏_55 demo = new 跳跃游戏_55();
        int[] nums = new int[]{
                2,3,1,1,4
        };
        boolean b = demo.canJump1(nums);
        System.out.println(b);
    }

    /*
    * 解法1： 利用递归 + 回溯  超时了  进行剪枝 ---> 如何剪枝  不会剪 淦
    * */
    public boolean canJump(int[] nums) {

        return f(nums,0);
    }

    public boolean f (int[] nums,int index){
        if(index>=nums.length){
            return false;
        }
        if(index == nums.length-1){
            return true;
        }
        if(nums[index] == 0){
            return false;
        }
        /*
        * 可以跳跃的步数
        * */
        for(int i=nums[index];i>0;i--){
            if(index+i>=nums.length){
                continue;
            }
            if(f(nums,index+i)){
                return true;
            }
        }
        return false;
    }

    /*
    * 解法2 ： 利用贪心  计算每个元素可以到达的最远位置
    * */
    public boolean canJump1(int[] nums){
        int nowMaxLength =0;
        for(int i=0;i<=nowMaxLength;i++){
            nowMaxLength = Math.max(nowMaxLength,i+nums[i]); // 当前可以到达的最远位置
            if(nowMaxLength >= nums.length-1)
                return true;
        }

        return false;
    }

}
